package DataStructures.BinaryTree;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/21 19:33
 * @description：二叉树的遍历
 * @modified By：
 * @version: $
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        Hero root = new Hero(1, "宋江");
        Hero hero1 = new Hero(2, "吴用");
        Hero hero2 = new Hero(3, "卢俊义");
        Hero hero3 = new Hero(4, "林冲");
        HeroList binaryTree = new HeroList();
        root.setLeft(hero1);
        root.setRight(hero2);
        hero2.setRight(hero3);
        binaryTree.setHead(root);
        System.out.println("前序遍历：");
        binaryTree.preOrder();
//        System.out.println("中序遍历：");
//        binaryTree.midOrder();
//        System.out.println("后序遍历：");
//        binaryTree.postOrder();
//        System.out.println("前序查找:");
//        System.out.println(binaryTree.preFind(1));
//        System.out.println("中序查找:");
//        System.out.println(binaryTree.midFind(3));
//        System.out.println("后序查找:");
//        System.out.println(binaryTree.postFind(4));
        System.out.println("删除后");
        binaryTree.del(3);
        binaryTree.preOrder();
    }


}

class Hero {
    private int id;
    private String name;
    private Hero left;
    private Hero right;

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public Hero() {
    }

    public Hero(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public void setLeft(Hero left) {
        this.left = left;
    }

    public void setRight(Hero right) {
        this.right = right;
    }

    public Hero getLeft() {
        return left;
    }

    public Hero getRight() {
        return right;
    }

    public void setId(int id) {
        this.id = id;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Hero{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历二叉树
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历二叉树
    public void midOrder() {

        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    //后序遍历二叉树
    public void postOrder() {

        if (this.left != null) {
            this.left.postOrder();
        }

        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序查找
    public Hero preFind(int no){
        Hero res = null;
        if (this.id == no){
            return this;
        }
        if (this.left!= null){
            res = this.left.preFind(no);
        }
        //可以减少不必要的查找时间，如果左边找到就直接返回
        if (res!=null){
            return res;
        }
        if (this.right != null){
            res = this.right.preFind(no);
        }
        return res;

    }
    //中序查找
    public Hero midFind(int no){
        Hero res = null;

        if (this.left!= null){
            res = this.left.preFind(no);
        }
        //可以减少不必要的查找时间，如果左边找到就直接返回
        if (res!=null){
            return res;
        }
        if (this.id == no){
            return this;
        }

        if (this.right != null){
            res = this.right.preFind(no);
        }
        return res;

    }
    //后序查找
    public Hero postFind(int no){
        Hero res = null;

        if (this.left!= null){
            res = this.left.preFind(no);
        }
        //可以减少不必要的查找时间，如果左边找到就直接返回
        if (res!=null){
            return res;
        }
        if (this.right != null){
            res = this.right.preFind(no);
        }
        //可以减少不必要的查找时间，如果左边找到就直接返回
        if (res!=null){
            return res;
        }
        if (this.id == no){
            return this;
        }
        return res;

    }
    //删除节点
    public void del(int no){

        if (this.left!= null && this.getLeft().getId() == no){
            this.setLeft(null);
            return;
        }
        if (this.right != null && this.getRight().getId() == no){
            this.setRight(null);
            return;
        }
        if (this.left!= null){
            this.left.del(no);
        }
        if (this.right != null){
            this.right.del(no);
        }
    }

}

class HeroList {
    private Hero head;

    public HeroList() {
    }

    public void setHead(Hero head) {
        this.head = head;
    }

    //前序遍历
    public void preOrder() {
        if (head == null) {
            System.out.println("二叉树为空!");
        } else {
            head.preOrder();
        }

    }

    //中序遍历
    public void midOrder() {
        if (head == null) {
            System.out.println("二叉树为空!");
        } else {
            head.midOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (head == null) {
            System.out.println("二叉树为空!");
        } else {
            head.postOrder();
        }
    }

    //前序查找
    public Hero preFind(int no){
       return head.preFind(no);
    }
    //前序查找
    public Hero midFind(int no){
        return head.midFind(no);
    }
    //前序查找
    public Hero postFind(int no){
        return head.postFind(no);
    }

    /**
     * 删除节点，如果节点为叶子节点就直接删除，如果不是叶子节点就将整颗树删除
     * @param no
     */
    public void del(int no){
        if (this == null){
            return;
        }
        if (this.head.getId() == no){
            this.head = null;
        }else {
            this.head.del(no);
        }
    }

}